package leetcode

import kotlinetc.createNodeList
import kotlinetc.println
import kotlinetc.toList

//https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
/**
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:

Input: 1->1->1->2->3
Output: 2->3
 */
fun main(args: Array<String>) {

    var nodeList = createNodeList("1->2->3->3->4->4->5->5")


    nodeList.toList().println()

    deleteDuplicates(nodeList).toList().println()
}


fun deleteDuplicates(head: ListNode?): ListNode? {


    var p = head

    var h: ListNode? = null
    var prev: ListNode? = null
    while (p?.next != null) {

        if (p.`val` == p.next?.`val`) {

            if (p == h) //如果新开始的节点开始发生重复，且是头，那么头置空
                h = null

            while (p?.next != null && p?.next?.`val` == p?.`val`)
                p = p?.next

            p = p?.next

            prev?.next = p

        } else {

            if (h == null) //header
                h = p

            prev = p  //保存前一个节点
            p = p.next //往后移动
        }

    }

    //2,2,3,3,5 最后直接到最后一个节点退出，此时头就是最后一个节点 即p
    return h ?: p
}

